#include <iostream>
#include <fstream>
#include <limits>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
using std::pair;

template <typename Key, typename Value>
class PriorityQueue {
public:
        PriorityQueue() {};
        ~PriorityQueue() {};
        void changeKey(Key key, Value value);
        void push(Key key, Value value);
        Value pop();
        void deleteValue(Value value);
        bool containValue(Value value);
        bool empty();
		//Key getKey(Value value);
        size_t size() { return mMap.size();}
private:
        multimap<Key, Value> mMap;
		map <Value, typename multimap<Key, Value>::iterator> Value2IterMap; 
};

template <typename Key, typename Value>
void PriorityQueue<Key, Value>::push(Key key, Value value) {
       multimap<Key,Value>::iterator itr=mMap.insert(pair<Key, Value>(key, value));
	   Value2IterMap.insert(pair <Value, typename multimap<Key,Value>::iterator>( value, itr ));
}

/*template <typename Key, typename Value>
Key PriorityQueue<Key, Value>::getKey(Value value) {
        return mMap[value];
}*/

template <typename Key, typename Value>
Value PriorityQueue<Key, Value>::pop() {
        Value val = mMap.begin()->second;
		Value2IterMap.erase(val);
		mMap.erase(mMap.begin());
		return val;
}

template <typename Key, typename Value>
void PriorityQueue<Key, Value>::changeKey(Key key, Value value) {
       /*for  (multimap<Key, Value>::iterator itr = mMap.begin(); itr!=mMap.end(); itr++) {
		   if (itr->second == value) {
			   mMap.erase(itr);
			   mMap.insert(pair<Key, Value>(key, value));
			   break;
		   }
	   }*/

	   map<Value, typename multimap<Key,Value>::iterator>::iterator itr = Value2IterMap.find(value);
	   if (itr != Value2IterMap.end()) {
                        mMap.erase(itr->second);
                        Value2IterMap.erase(itr);
                        push(key, value);
                }
                
}

template <typename Key, typename Value>
bool PriorityQueue<Key, Value>::containValue(Value value) {
        /*for  (multimap<Key, Value>::iterator itr = mMap.begin(); itr!=mMap.end(); itr++) {
		   if (itr->second == value) {
			   return true;
		   }
	   }
		return false;*/
	return (Value2IterMap.find(value)!=Value2IterMap.end());
}

template <typename Key, typename Value>
void PriorityQueue<Key, Value>::deleteValue(Value value) {
        /*for  (multimap<Key, Value>::iterator itr = mMap.begin(); itr!=mMap.end(); itr++) {
		   if (itr->second == value) {
			   mMap.erase(itr);
			   break;
		   }
	   }*/

	map<Value, typename multimap<Key,Value>::iterator>::iterator itr = Value2IterMap.find(value);
	   if (itr != Value2IterMap.end()) {
                        mMap.erase(itr->second);
                        Value2IterMap.erase(itr);
         
                }
}



template <typename Key, typename Value>
bool PriorityQueue<Key, Value>::empty() {
        return mMap.empty();
}